Grokking LinkedIn Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
LinkedIn Easy
Find Pivot Index (easy)
Solution: Find Pivot Index
Isomorphic Strings (easy)
Solution: Isomorphic Strings
Second Minimum Node In a Binary Tree (easy)
Solution: Second Minimum Node In a Binary Tree
Minimum Time to Type Word Using Special Typewriter (easy)
Solution: Minimum Time to Type Word Using Special Typewriter
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Can Place Flowers (easy)
Solution: Can Place Flowers
Valid Perfect Square (easy)
Solution: Valid Perfect Square
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Sqrt (easy)
Solution: Sqrt
Valid Palindrome (easy)
Solution: Valid Palindrome
Rotate List (medium)
Solution: Rotate List
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Valid Triangle Number (medium)
Solution: Valid Triangle Number
Valid Parenthesis String (medium)
Solution: Valid Parenthesis String
Edit Distance (medium)
Solution: Edit Distance
Remove All Ones With Row and Column Flips II (medium)
Solution: Remove All Ones With Row and Column Flips II
Reverse Integer (medium)
Solution: Reverse Integer
Triplet Sum to Zero (medium)
Solution: Triplet Sum to Zero
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Decode Ways (medium)
Solution: Decode Ways
Quadruple Sum to Target (medium)
Solution: Quadruple Sum to Target
Next Permutation (medium)
Solution: Next Permutation
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Word Search (medium)
Solution: Word Search
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
House Robber II (medium)
Solution: House Robber II
Coin Change
Solution: Coin Change
Design Add and Search Words Data Structure (medium)
Solution: Design Add and Search Words Data Structure
Merge Intervals (medium)
Solution: Merge Intervals
Number of Islands (easy)
Solution: Number of Islands
Longest Palindromic Subsequence (medium)
Solution: Longest Palindromic Subsequence
Kth Smallest Number (medium)
Solution: Kth Smallest Number
Maximum Product Subarray (medium)
Solution: Maximum Product Subarray
Same Tree (medium)
Solution: Same Tree
Max Points on a Line (hard)
Solution: Max Points on a Line
Closest Binary Search Tree Value II (hard)
Solution: Closest Binary Search Tree Value II
Word Ladder (hard)
Solution: Word Ladder
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Solution: Intersection of Two Arrays

Problem Statement

Given two arrays, nums1 and nums2 containing integers, return an array of the intersection of nums1 and nums2. In the resultant array, each integer should be unique, and elements can be in any order.

Examples

  • Example 1:

    • Input: nums1 = [3,1,2,6,7,8], nums2 = [2,3,4,5,7,9]
    • Expected Output: [2,3,7]
    • Justification: The numbers 2, 3, and 7 are present in both nums1 and nums2.
  • Example 2:

    • Input: nums1 = [1,2,3], nums2 = [4,5,6]
    • Expected Output: []
    • Justification: There are no common elements between nums1 and nums2, hence the output is an empty array.
  • Example 3:

    • Input: nums1 = [7,8,9,10], nums2 = [10,9,8,7]
    • Expected Output: [7,8,9,10]
    • Justification: All elements from nums1 are present in nums2 and vice versa.

Solution

To solve this problem, we will utilize a set-based approach. Sets are ideal for this task because they automatically remove duplicate elements and allow for efficient element lookup. First, we'll convert both input arrays into sets. This conversion eliminates any duplicates within each array, aligning with our requirement to return only unique common elements. Then, we'll find the intersection of these two sets, which gives us the set of elements present in both arrays. This method is effective because set operations are generally more efficient than iterating through arrays, especially when dealing with duplicates and the need for uniqueness. Our approach reduces the problem to simple set operations, making the solution more elegant and performant.

The rationale behind using sets over other data structures is twofold. Firstly, the automatic removal of duplicates simplifies our task. Secondly, the intersection operation directly corresponds to our goal of finding common elements, ensuring that the algorithm is both intuitive and efficient.

Step-by-step Algorithm

  1. Initialize Two Sets: Start by creating two empty sets, set1 and set2. These will store the unique elements from nums1 and nums2, respectively.
  2. Populate the First Set (set1): Loop through each element in nums1. For every element, add it to set1. This step ensures that set1 contains all unique elements from nums1.
  3. Populate the Second Set (set2): Repeat the process for nums2, adding each of its elements to set2. Now, set2 contains all unique elements from nums2.
  4. Find Intersection: Identify the common elements between set1 and set2. This can be done by checking each element of set1 to see if it also exists in set2, or by utilizing set intersection operations available in many programming languages.
  5. Prepare the Result: Convert the intersection set into an array. This step involves initializing an array and populating it with the elements from the intersection set.
  6. Return the Result: Finally, return the array created in the previous step. This array contains all unique elements that are present in both nums1 and nums2.

Algorithm Walkthrough with Input

Given nums1 = [3,1,2,6,7,8], nums2 = [2,3,4,5,7,9]:

  1. Initialize Sets:

    • set1 = {}
    • set2 = {}
  2. Populate set1:

    • Loop through nums1: add 3, 1, 2, 6, 7, and 8 to set1.
    • After the loop, set1 = {1, 2, 3, 6, 7, 8}.
  3. Populate set2:

    • Loop through nums2: add 2, 3, 4, 5, 7, and 9 to set2.
    • After the loop, set2 = {2, 3, 4, 5, 7, 9}.
  4. Find Intersection:

    • Identify common elements between set1 and set2.
    • Intersection: {2, 3, 7}.
  5. Prepare the Result:

    • Convert the intersection set to an array: [2, 3, 7].
  6. Return the Result:

    • The final result is [2, 3, 7], which is the array of unique elements present in both nums1 and nums2.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity:

  • Creating Sets: for the first array and for the second, where n and m are the lengths of the two input arrays.
  • Finding Intersection: Iterating through the smaller set and checking for each element in the larger set, leading to in the best case and in the worst case.

Thus, the overall time complexity combines these steps, resulting in .

Space Complexity:

  • Space is required for storing elements of both arrays in sets, leading to a space complexity of in the worst case when all elements are unique.
Intersection of Two Arrays (easy)
Can Place Flowers (easy)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough with Input

Code

Complexity Analysis

Time Complexity:

Space Complexity: